package com.power.algorithm;

import java.util.HashSet;
import java.util.Objects;
import java.util.Set;
import java.util.Stack;

/**
 * @description:
 * @author: jiangnan
 * @time: 2021/6/21 4:23 下午
 */
public class LinkedList {
    Node head;
    int size = 0;

    class Node {
        int val;
        Node next;

        public Node(int val) {
            this.val = val;
        }
    }

    public void add(int val) {
        Node newNode = new Node(val);
        if (head == null) {
            head = newNode;
        } else {
            Node tmp = head;
            while (tmp.next != null) {
                tmp = tmp.next;
            }
            tmp.next = newNode;
        }
        size++;
    }


    public void remove(int value) {
        Node tmp = head;
        while (tmp.next != null) {
            if (tmp.val == value) {
                tmp.val = tmp.next.val;
                tmp.next = tmp.next.next;
                System.out.println("删除节点值为::" + value);
                return;
            }
            tmp = tmp.next;
        }
        size--;
    }

    //采用栈的方式进行翻转
    public void reverse() {
        Node result = null;
        int n = 0;
        Stack<Node> stack = new Stack<>();
        Node tmp = head;
        //将所有的节点放到栈里面
        for (int i = 0; i < size; i++) {
            stack.push(new Node(tmp.val));
            tmp = tmp.next;
        }

        //栈不为空的话   就出站就组成队列
        while (stack.size() > 0) {
            if (result == null) {
                result = stack.pop();

            } else {
                //如果新的链表不为空  则出站进行赋值
                Node tmp2 = result;
                while (tmp2.next != null) {
                    tmp2 = tmp2.next;
                }
                tmp2.next = stack.pop();
            }
            n++;
        }
        System.out.println("栈的方式翻转节点");
        display(result, n);
    }

    //采用双链表的形式进行
    public void reverse2() {
        Node result = null;
        Node tmp = head;
        int n = 0;
        for (int i = 0; i < size; i++) {
            Node node = new Node(tmp.val);
            if (result == null) {
                result = node;
            } else {
                node.next = result;
                result = node;
            }
            n++;
            tmp = tmp.next;
        }
        System.out.println("双链表翻转节点");
        display(result, n);
    }

    /**
     * 1. 递归终止条件
     * 2. 逻辑处理
     * 3. 递归函数
     * 4. 逻辑处理
     */
    //递归调用翻转字符串
    public Node reverse3(Node head) {
        //终止条件
        if (head == null || head.next == null) {
            return head;
        }
        //逻辑处理
        //保存当前节点的下一个节点
        Node newHead = reverse3(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }

    //采用快慢指针查看是否相遇
    public boolean checkCycle(Node head) {
        if (head == null || head.next == null) {
            return false;
        }
        Node tmp = head;
        Node fast = tmp.next.next;
        Node slow = tmp;
        while (tmp != null) {
            if (Objects.equals(slow, fast)) {
                return true;
            }
            tmp = tmp.next;
            fast = fast.next.next;
            slow = slow.next;
        }
        return false;
    }

    //采用Set的方式遍历
    public boolean checkCycle2(Node head) {
        Node tmp = head;
        Set set = new HashSet<Node>();

        while (tmp.next != null) {
            if(set.contains(tmp)){
                return true;
            }
            tmp = tmp.next;
        }
        return false;
    }
    //
    public boolean checkCycle3() {

        return false;
    }

    public void deleteBackWardNNode(Node head, int N) {

    }

    public void display(Node node, int size) {
        System.out.print("链表节点:: ");
        for (int i = 0; i < size; i++) {
            System.out.print(" " + node.val);
            node = node.next;
        }
        System.out.println("\n");
    }

    public void display() {
        Node tmp = head;
        System.out.print("节点   ");
        for (int i = 0; i < size; i++) {
            System.out.print(" " + tmp.val);
            tmp = tmp.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();

        for (int i = 0; i < 10; i++) {
            list.add(i);
        }
        list.display();
//        list.remove(5);
//        list.display(list.head);

        list.reverse();
        list.reverse2();
        Node reverse3 = list.reverse3(list.head);
        list.display(reverse3, 10);
        //  list.display();
        System.out.println(list.checkCycle(list.head));
        System.out.println(list.checkCycle2(list.head));
    }
}
